Image pattern recognition is used in a variety of application such as identifying bar codes and/or other image based codes such as QR codes. One feature of such codes is that they often comprise a pattern of black or white portions. The pattern results in a black or white image portion extending in a direction some length before it changes, e.g., to the opposite value in the case of binary image values.
How long a black or white portion of an image continues can be used in determining the pattern to which an image corresponds. An efficient way of representing how long of a sequence occurs in which an image pixel remains the same is by representing the information as a run length, e.g., for a given pixel value the run length indicates how long, in terms of the number of pixel locations, the pixel value remains unchanged.
In processing images representing bar codes, QR codes and/or other binary patterns for pattern recognition purposes it may be desirable to compute vertical pixel value run lengths for the full set of pixel values in an image.
In a naïve approach to calculate vertical run lengths in a binary image, pixels are compared vertically against one another for a first individual vertical column in the image until the comparisons for the first individual column are completed. Then, pixels are compared vertically against one another for a next individual vertical column in the image until the comparisons for the next individual column are completed. The process is repeated until each of the columns of the image have been processed to obtain vertical run lengths for the image.
This approach results in vertical run lengths for a first column being computed before the vertical run lengths for the next column are computed. While this approach can be effective in ultimately computing vertical run lengths, it has several technical disadvantages associated with the memory access process and may result in a large amount of data being moved in and out of cache memory as the vertical run lengths are computed given that binary bitmaps of pixel values are normally stored horizontally in memory and the cache memory is often unable to store all the row and columns of image data in the cache memory at once. Given the horizontal storage of pixel values, data corresponding to a row of pixels can normally be read out using sequential reads by sequentially incrementing the read address used to control readout of data from memory. In the case of reading out of data corresponding to different rows of a column the data is often spaced further apart in memory than the data corresponding to a row of pixel values. In fact, the data corresponding to the last row of pixel values may not fit in a cache memory with the data corresponding to the first row of pixel values of an image when row data is stored in sequential memory location as is normally the case.
This approach can result in long processing delays in determining vertical run lengths as rows of pixel values are moved in and out of cache memory to allow for computation of the vertical run lengths corresponding to the first row before proceeding to computing vertical run lengths for the next row of pixel values.
In image processing devices with relatively small caches, e.g., low cost handheld devices, the cache memory may exhibit thrashing as the memory location accesses, performed in the vertical run length determinations, jump by large steps for each iteration potentially requiring image data to be moved in and out of cache memory.
Based on the above discussion, there is a need for new methods and apparatus for efficiently determining vertical run lengths of pixel values. It would be desirable if the new methods and/or apparatus were well suited for devices with limited caches, e.g., handheld devices, which may not be able to fit the entire contents of an image of a code upon which pattern recognition is to be formed in the cache at the same time.